The present invention relates compression/decompression means of an image, and relates to techniques for improving a compression ratio, for example, when an image is compressed by MR coding and MMR coding of Comite Consultatif International Telegraphique et Telephonique (CCITT) international standard used in an information unit such as a facsimile unit.
Various types of information processing units having an image information processing function in addition to a conventional character code processing function have been widely spread in recent years due to the improvement of computer processing capability, appearance of a large capacity memory and so on.
In office automation, there are various types of equipment such as a facsimile unit, a digital copying machine, a desk top publishing unit and an image filing unit that serve as products applied with image processing techniques. In these types of equipment, even if a large capacity memory appears and a communication medium having high speed data transmitting function is developed, image data is stored after compression processing and transmitted in many cases because the capacity of image data is large. For example, even image data in A4 size having density of 200 Dot Per Inch (DPI) has a data capacity as large as approximately 500 Kbytes, and as for the image data in A3 size having density of 400 DPI, even data capacity of approximately 4 Mbytes is shown. Furthermore, even when 29 lines' worth of 36 characters (36.times.29=1,044 characters) are written in a full page of A4 size, the character code reaches approximately 2 Kbytes (1,044.times.2=2,088 bytes assuming one character includes 2 bytes) at most.
Now, as typical compression processing system of an image, there are a Modified Huffman (MH) scheme, a Modified Relative Element Address Designate (MR) scheme, a Modified MR (MMR) scheme and so on of CCITT international standard used in a facsimile unit. As to these schemes and apparatus for realizing the same, detailed description is made in JP-A-59-126368 for instance.
FIG. 2 is a diagram for briefly explaining the MMR scheme having the highest compression ratio among these three types of schemes.
The whole image is scanned horizontally starting from the left upper corner towards the right, data is input dot by dot, and further, horizontal scanning is made from top to bottom, and image data for each scanning line is input successively.
Further, the contents of an image, i.e., black dots (normally referred to also as pixels) exist in such a manner that they are arranged in a form slightly deviating in a horizontal direction and a vertical direction from one another quite frequently. Compression processing is applied to such a list showing slight deviation by assigning short codes.
There are three types of well known methods of compression processing, which are referred to as "horizontal mode", "vertical mode" and "pass mode", respectively.
In the "horizontal mode", the run length of picture elements arranged in a horizontal direction is compressed and coded.
For example, such processing is performed that a binary number "11" having short data length is assigned to two black dots of the highest appearance frequency, and a binary number "000011001010" having long data length is assigned to 26 black dots of low appearance frequency in a manuscript for facsimile of CCITT international standard.
This horizontal mode is required in a portion where no color change occurs and there is no correlation in a vertical direction in the data on a scanning line one line above as shown at the uppermost end of an alphabetic character "A" shown in FIG. 2, and codes are assigned to four white dots from a dot 201 to a dot 202 and to six black dots from a dot 203 to a dot 204.
The "vertical mode" is a coding scheme in which codes are assigned to the deviation quantity of the black picture elements existing in two lines for compression.
Namely, when color change (from white to black, from black to white) occurs in data on a scanning line one line above, and the position where the color change is generated is slightly deviated in the next scanning line, the code is assigned to the deviation quantity. For example, such processing is performed that a binary number "011" is assigned in case of deviation to the right by one dot and a binary number "000010" is assigned in case of deviation to the left by two dots. In the standard, processing the codes corresponding to deviation quantity are specified up to the deviation by three dots to the left and to the right, respectively.
This vertical mode is processing required at an intermediate position of the alphabetic character "A", and a dot 206 is assigned with a code expressing the state that the black picture element is deviated to the left by one dot with respect to a dot 205, and furthermore, a dot 208 is assigned with a code expressing the state that the white picture element is deviated to the left by two dots with respect to a dot 207 as shown in FIG. 2. Being different from the vertical mode, the pass mode encodes the state that continuity of the color change continued from the above line disappears on the scanning line which is an object of compression.
In FIG. 2, since black dots from a dot 209 to a dot 210 disappear in a dot 211 to a dot 212, a code in the pass mode is assigned to a dot 213. This pass mode has an effect of not generating a black dot erroneously in the vicinity of the dot 209 between the dot 211 and the dot 212 by a code in the vertical mode when an image in the vertical mode exists further on the right side of the dot 212.
Such a method of realizing image compression is described in JP-A-59-12368 for instance.
Although an MMR scheme as described above has been proposed as an international standard, the compression ratio is low in similar cases depending on the contents of the image, e.g., when the black dot exists in seclusion. Although it is almost impossible practically, the data quantity is increased to a multiple equal to almost approximately three times the original image data quantity in principle sometimes in the MMR scheme. As a result, various compression schemes, which have not been adopted as the standard, have been proposed.
In proposed various compression schemes, however, a satisfactory compression ratio is unobtainable for all of the images, and furthermore, a problem of data interchangeability is generated since neither of these schemes are standards.
In the MMR scheme among the above-described techniques, the data quantity of an image is compressed by utilizing characteristics of the image, and a mean value of the compression ratios of eight sheets of standard manuscripts for facsimile of CCITT international standard becomes approximately 1/15 times, thus it may be mentioned to be a superior scheme. Further, the scheme has data exchangeability with a plurality of units because of the international standard.
However, the compression data by the MMR scheme still has a large data quantity of approximately 33 Kbytes as compared with a character code in 2 Kbytes. Since image data includes more information such as the form of a character than the character code, it is impossible to compress the data to 2 Kbytes, but it is a matter of course that the compression ratio needs to be improved even if slightly when data transmission, storage or the like is taken into consideration.
In an original compression scheme other than the MR scheme and the MMR scheme, a problem exists in the interchangeability of data. There is such a problem that image data input by spending one's labor cannot be used in the other units.